package com.jeff.interview;

import java.util.HashMap;
import java.util.HashSet;
// 青蛙跳石子问题 采用了动态规划
public class FrogJump {
    public boolean canCross(int[] stones) {
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int stone : stones) {
            map.put(stone, new HashSet<>());
        }
        map.get(stones[0]).add(1); // 从第一个石头开始，青蛙可以跳 1 个单位

        for (int stone : stones) {
            for (int jump : map.get(stone)) {
                // 尝试跳 k-1, k, k+1
                for (int nextJump = jump - 1; nextJump <= jump + 1; nextJump++) {
                    if (nextJump > 0) { // 跳跃距离不能为负
                        int nextStone = stone + nextJump;
                        if (map.containsKey(nextStone)) { // 如果下一个石子存在
                            map.get(nextStone).add(nextJump);
                        }
                    }
                }
            }
        }

        return !map.get(stones[stones.length - 1]).isEmpty(); // 如果最后一块石子可以到达，返回 true
    }

    public static void main(String[] args) {
        FrogJump frogJump = new FrogJump();
        int[] stones1 = {0, 1, 3, 5, 6, 8, 12, 17};
        System.out.println(frogJump.canCross(stones1)); // 输出: true

        int[] stones2 = {0, 1, 2, 3, 4, 8, 9, 11};
        System.out.println(frogJump.canCross(stones2)); // 输出: false
    }
}
